package myjava.algorithm;

import java.util.*;

import javax.lang.model.type.NullType;

public class Subset {
	
	public static void dfs(int[] S,int start,List<Integer> item,List<List<Integer>> resultLists)
	{
		for(int i=start;i<S.length;i++)
		{
			item.add(S[i]);
			resultLists.add(new ArrayList<Integer>(item));
			dfs(S, i+1, item, resultLists);
			item.remove(item.size() - 1);
			
			
			while(i<(S.length-1)&&S[i]==S[i+1]) {  
                i++;  
            } 
            
		}
	}
	
	public static List<List<Integer>> subsets(int[] S) {
		
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> items = new ArrayList<Integer>();
		
		if(S.length == 0 || S == null)
		{
			return result;
		}
		Arrays.sort(S);
		
		dfs(S,0,items,result);
		
		result.add(new ArrayList<Integer>());
				
        return result;
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] abc = {1,1,1,4,5,6};
		List<List<Integer>> resultList = subsets(abc);
		
		for(List<Integer> listInteger : resultList)
		{
			for(Integer k : listInteger)
			{
				System.out.print(k + " ");
			}
			System.out.println();
		}
	}

}
